import java.util.*;

public class AkariDaisukiDiv1 {

	private String f(String x) {
		return Waai + x + Akari + x + Daisuki;
	}
	
	String Waai; String Akari; String Daisuki;
		
	
	private boolean eqSub(String x, int start, int len, String f) {
		for (int i=0; i<len; i++) if (x.charAt(i+start) != f.charAt(i)) return false;
		return true;
	}
	
	private int bare(String x, String F) {				
		if (x.length() < F.length()) return 0;
		int res = 0;
		for (int i=0; i<=x.length() - F.length(); i++) if (eqSub(x, i, F.length(), F)) res++;
		return res;
	}
	
	private int[] suffix(String x, String F) {
		int [] res = new int[F.length()];
		for (int i=1; i<=Math.min(res.length-1, x.length()); i++)
			if (eqSub(x, x.length()-i, i, F)) res[i] = 1;
		return res;
	}
	
	private int[] prefix(String x, String F) {
		int [] res = new int[F.length()];
		for (int i=1; i<=Math.min(res.length-1, x.length()); i++)
			if (eqSub(F, F.length()-i, i, x)) res[i] = 1;
		return res;
	}
	
	private int[] infix(String x, String F) {
		int [] res = new int[F.length()];
		
		for (int i=1; i<=res.length - x.length(); i++)
			if (eqSub(F, i, x.length(), x)) res[i] = 1;
		return res;
	}
	
	public int countF(String Waai, String Akari, String Daisuki, String S, String F, int k) {
		this.Waai = Waai;
		this.Akari = Akari;
		this.Daisuki = Daisuki;
		
		String x = S;
		while (k > 0 && x.length() < F.length()) {
			x = f(x);
			k--;
		}
		if (k == 0 && x.length() < F.length()) return 0;
		
		int f = bare(x, F);
		int wres = bare(Waai, F);
		int ares = bare(Akari, F);
		int dres = bare(Daisuki, F);
		
		int[] sufW = suffix(Waai, F);
		int[] prefD = prefix(Daisuki, F);
		
		int[] sufA = suffix(Akari, F);
		int[] prefA = prefix(Akari, F);
		int[] infA = infix(Akari, F);
		
		int [] sufX = suffix(x, F);
		int [] prefX = prefix(x, F);
		
		String x0 = x;
		String prefXAcc = x0;
		String sufXAcc = x0;
		
		int stabilizedLen = 0;
		boolean stabilizedPrefix = false;
		boolean stabilizedSuffix = false;
		for (int i=0; i<k; i++) {
			int fnxt = 2*f + wres + ares + dres;
			
			if (!(stabilizedPrefix && stabilizedSuffix)) {				
		      stabilizedLen = 0;
			  for (int j=1; j<F.length(); j++) {
				
				if ((sufW[j] & prefX[F.length()-j]) == 1) stabilizedLen++;
				if ((sufX[j] & prefA[F.length()-j]) == 1) stabilizedLen++;
				if ((sufA[j] & prefX[F.length()-j]) == 1) stabilizedLen++;
				//infix
				if ((F.length() - j - Akari.length() >= 0) && ((sufX[j] & infA[j] & prefX[F.length() - j - Akari.length()]) == 1)) stabilizedLen++;
				if ((sufX[j] & prefD[F.length()-j]) == 1) stabilizedLen++;
			  }
			}
			fnxt += stabilizedLen;
			
			if (Waai.length() * i < F.length()) {
				prefXAcc = Waai + prefXAcc;
				prefX = prefix(prefXAcc, F);
			} else {
				stabilizedPrefix = true;
			}
			
			if (Daisuki.length() * i < F.length()) {
				sufXAcc = sufXAcc + Daisuki;
				sufX = suffix(sufXAcc, F);
			} else {
				stabilizedSuffix = true;
			}
			
			f = fnxt % 1000000007;
			//if (i% 1000 == 0) System.out.println(i);
		}
	
		return f;		
	}

}
